package com.直方图内最大的矩形状;
/*有一个直方图，用一个整数数组表示，其中每列的宽度为1，求所给直方图包含的最大矩形面积。
 * 比如，对于直方图[2,7,9,4],它所包含的最大矩形的面积为14(即[7,9]包涵的7x2的矩形)。
  给定一个直方图A及它的总宽度n，请返回最大矩形面积。
  保证直方图宽度小于等于500。保证结果在int范围内。
测试样例：
[2,7,9,4,1],5
返回：14

 * */
public class MaxInnerRec {
	 public int countArea(int[] A, int n) {
		 int max=0;
		 int s=0;
		 int temp=0;
		 for(int i=0;i<n;i++) {
			 if(temp<A[i])
				 temp=A[i];
		 }
		 max=temp;//单个矩阵中最大的那个
		 int partmin=0;//用于比较子问题时候的最小的值
		 for(int i=2;i<=n;i++) {//i代表矩形底的宽度，底为1已经算过了
			 for(int j=0;j<n&&j+i-1<n;j++) {
				 partmin = A[j];
				 for(int k=j;k<j+i&&k<n;k++) {
					   if(A[k]<partmin)
						   partmin=A[k];
				 }
				 s=partmin*i;
				 if(max<s)
					max=s;
			 }
		 }
	        return max;
	    }
}
